Dưới thời Vladimir Putin trong 2 nhiệm kỳ đầu, lập trường của điện Kremlin về Stalin dẫn đến việc từ từ khôi phục lại tiếng tăm của Stalin vào đầu những năm 2000. Khi Medvedev lên làm Tổng thống Nga, sự xích lại gần với Phương Tây, thôi thúc Nga thừa nhận một số tội ác của chế độ toàn trị Xô viết. Vào ngày 30 tháng 10 năm 2009- ngày truyền thống của Nga kỷ niệm những nạn nhân của sự đàn áp Xô viết - Medvedev đưa lên một videoblog lên án "những tội ác của Stalin" mà ông nhắc đến như "một trong những thảm kịch lớn nhất trong lịch sử nước Nga." [20],[21]

Kỷ niệm lần thứ 70 thảm sát Katyn vào ngày 7 tháng 4 năm 2010, Putin nói trong bài diễn văn: "những cuộc đàn áp nghiền nát nhân dân bất kể quốc tịch nào, tôn giáo nào, hay tín ngưỡng nào...Chúng ta không thể thay đổi quá khứ, nhưng những gì chúng ta có thể làm là giữ gìn hay khôi phục lại sự thật và điều này có nghĩa là khôi phục lại sự công bằng lịch sử."

Vào tháng Năm, Kremlin hủy bỏ một kế hoạch của chính quyền thành phố Moskva định trang hoàng Moskva bằng những hình ảnh của Stalin nhân dịp kỷ niệm lần thứ 65 chiến thắng phát xít Đức. Medvedev giải thích trong cuộc trả lời phỏng vấn của Izvestia: "đánh giá của nhà nước" về Stalin là ông ta đã "phạm nhiều tội ác chống nhân dân mình. Và mặc dầu đất nước giành được thắng lợi dưới sự lãnh đạo của ông, những gì ông ta đã làm chống lại nhân dân là không thể tha thứ."

Ngày 26 tháng 11, Nghị viện Nga (Duma) lần đầu tiên công bố chính thức, "Tội ác Katyn phạm theo lệnh trực tiếp của Stalin và những nhà lãnh đạo khác của Liên xô". Tổng thống Nga Medvedev nói với truyền thông Ba Lan trước một cuộc viếng thăm Warsaw trong tháng 12 "Stalin và tay sai của ông ta phải chịu trách nhiệm về tội ác này."